import java.util.Arrays;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: YKH
 * Date: 2022-05-28
 * Time: 13:24
 * author:MySort
 */
public class MySort {
    //插入排序
    /**
     时间复杂度：最坏情况 ： O(n^2)
               最好情况 ： O(n)
     空间复杂度： O(1)
     稳定性 ： 稳定
    */
    public static void insertSort(int []arr) {
        int i,j;
        for( i=1;i<arr.length;i++) {
            int tmp = arr[i];
            for(j=i-1;j>=0;j--) {
                if( arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    //希尔排序
    //思想 : 数据分组进行直接插入排序 , 逐渐减小分组的数量,数据会逐步趋于有序 , 直到为1组进行插入排序,运行效率提高
    //稳定性: 不稳定
    public static void shell(int []arr,int grp) {
        int i,j;
        for( i=grp; i< arr.length; i++) {
            int tmp = arr[i];
            for( j=i-grp; j>=0 ;j-=grp) {
                if(arr[j] > tmp) {
                    arr[j+grp] = arr[j] ;
                } else {
                    break;
                }
            }
            arr[j+grp] = tmp;
        }
    }
    public static void shellSort(int []arr) {
        int grp = arr.length;
        while( grp>1) {
            //对每组数据进行直接插入排序
            shell(arr,grp);
            grp /=2;
        }
        //对最后一组数据进行插入排序
        shell(arr,1);
    }

    //选择排序
    //思想 : 从数据头开始 , 往后遍历 ,将最小的数字记录下来 ,遍历结束和待排序的数字进行交换.
    //时间复杂度: O(n^2)
    //空间复杂度: O(1)
    //稳定性 : 不稳定
    public static void selectSort(int []arr) {
        int i,j;
        for(i=0;i<arr.length;i++) {
            //记录待排序数据的下标
            int minindex = i;
            for(j=i+1;j<arr.length;j++) {
                if( arr[j] < arr[minindex]) {
                    //记录最小数据的下标
                    minindex = j;
                }
            }
            //此时 arr[minindex] 存放最小的数据 , 与待排序数据交换
            int tmp = arr[i];
            arr[i] = arr[minindex];
            arr[minindex] = tmp;
        }
    }

    //堆排序


    //冒泡排序

    /**
     * 快速排序未优化
     * 时间复杂度 :
     *   最好情况 : 满二叉树 : O(n*logn)
     *   最坏情况 : 单分支树 , 树的高度等于元素的个数 : O(n^2)
     * 空间复杂度 :  O(logn) 递归的
     * 稳定性 : 不稳定
     */
    //求基准 方法一: Hoare法
    public static int partition1(int []arr ,int low ,int high) {
        //记录当前基准的位置
        int i = low;
        //记录基准值,用于比较
        int tmp = arr[low];
        //基准如果选择的左边 , 要先从 右往左找 , 否则
        while( low < high) {
            //从右左找比基准小的位置
            while( low < high && arr[high] >= tmp) {
                high--;
            }
            //从左往右找比 基准大的值的位置
            while( low < high && arr[low] <= tmp) {
                low++;
            }

            //找到后交换
            swap(arr,low,high);
        }
        //当low = high 时出循环,说明low和high相遇,交换基准值和 相遇位置的值
        swap(arr,i,low);
        //交换完毕后,基准值的下标 就是low
        return low;
    }

    //求基准方法二 挖坑法
    public static int partition2(int []arr ,int low ,int high) {
        int tmp = arr[low];

        while( low <high) {
            while( low <high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high];
            while( low <high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = tmp;
        return low;
    }

    public static void quickSort(int []arr,int left ,int right) {
        if(left >= right) {
            return ;
        }
        int privot = partition2(arr,left,right);
        quickSort(arr,left,privot-1);
        quickSort(arr,privot+1,right);

    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void main(String[] args) {
        int []arr = { 10,9,4,55,1,14,5};
        System.out.println("排序前" +  Arrays.toString(arr) );
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);
        int right = arr.length-1;
        quickSort(arr,0,right);
        System.out.println("排序后" +  Arrays.toString(arr) );
    }
}
